package LinkedList;

import Node.ListNode;

/**
 * 92. 反转链表 II
 */
public class RecursionReverseBetweenList {

    public ListNode reverseBetween(ListNode head, int m, int n) {

        // base case
        if (m == 1) {
            return reverseN(head,n);
        }
        // 前进到反转的起点触发base case
        head.next = reverseBetween(head, m - 1, n - 1);
        return head;
    }

    // 后驱节点
    ListNode successor = null;

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        head.next = successor;
        return last;
    }
}
